package com.zzz.offer.oddeven;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class OddEven {

    public static void main(String[] args) {
        int[] array = new int[]{2, 4, 5, 1, 3, 6};

        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(new OddEven().reOrderArray(array)));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] reOrderArray(int[] array) {
        // write code here
        if (array.length == 0 || array.length == 1) {
            return array;
        }

        // 使用一个相同长度的数组空间
        int[] count = new int[array.length];

        // 统计奇数个数 和 偶数个数
        // 使用 临时数组空间的第0个位置 和第一个位置 存储
        for (int item : array) {
            count[item & 1]++;
        }

        //因为奇数在前，所以奇数的存储下标应该是 0
        int oddIndex = 0;

        // 偶数的存储下标开始位置是 奇数的个数
        int evenIndex = count[1];


        // 保证奇数和奇数维持原来的位置
        // 遇到一个奇数就将其放入下标位置，然后下标位置 加1，准备放下一个奇数
        // 偶数也一样
        for (int item : array) {
            if ((item & 1) == 1)
                count[oddIndex++] = item;
            else
                count[evenIndex++] = item;
        }
        return count;
    }
}
